package com.javabasic.algorithm.leetcode;

import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;

import java.util.stream.Stream;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2023/12/19 21:36
 */
public class FindAPeakElementII {


    public static Stream<int[][]> testData() {
        int[][] ints = {{7, 2, 3, 1, 2}, {6, 5, 4, 2, 1}};
        return Stream.of(
                ints,
                ints
        );
    }

    @ParameterizedTest
    @MethodSource("testData")
    public void findPeakGridTest(int[][] mat) {
        int[] peakGrid = findPeakGrid(mat);
        for (int i : peakGrid) {
            System.out.printf("%d ", i);
        }
    }

    /**
     * 二分法
     *  以数组维度二分查找，每一行的最大值肯定是峰值的候选，设有m行n列，
     *  我们可以用O(n)的时间寻找一行的最大值，然后二分地用O(log m)的时间搜索m列，
     *  当第i行的最值小于上一行这一列的数时，我们便将搜索范围缩小为第i行上面的部分；
     *  当第i行的最值小于下一行这一列的数时，便将搜索范围缩小为第i行下面的部分；
     *  都大于时便直接输出结果
     *
     *  link:
     *  - https://leetcode.cn/problems/find-a-peak-element-ii/solutions/2572645/1901-xun-zhao-feng-zhi-ii-ge-ren-bi-ji-b-4sp1/?envType=daily-question&envId=2023-12-19
     *  - https://leetcode.cn/problems/find-a-peak-element-ii/solutions/2572644/er-fen-cha-zhao-jie-jue-xun-zhao-feng-zh-r587/?envType=daily-question&envId=2023-12-19
     *
     * @param mat
     * @return
     */
    public int[] findPeakGrid(int[][] mat) {
        int row = mat.length;
        int col = mat[0].length;

        int maxValue = -1;
        int tagX = -1;
        int tagY = -1;
        if (row == 1) {
            maxValue = -1;
            for (int j = 0; j < col; j++) {
                if (mat[0][j] < maxValue) {
                    continue;
                }
                maxValue = mat[0][j];
                tagY = j;
            }
            return new int[]{0,tagY};
        }


        int mid;
        int up = 0;
        int down = row - 1;
        while (up <= down) {
            mid = up + ((down - up) >> 1);
            maxValue = -1;
            tagX = -1;
            tagY = -1;
            for (int j = 0; j < col; j++) {
                if (mat[mid][j] < maxValue) {
                    continue;
                }
                maxValue = mat[mid][j];
                tagX = mid;
                tagY = j;
            }

            if (mid == 0) {
                if (mat[tagX+1][tagY] < maxValue) {
                    return new int[]{tagX, tagY};
                } else {
                    mid ++;
                    maxValue = -1;
                    for (int j = 0; j < col; j++) {
                        if (mat[mid][j] < maxValue) {
                            continue;
                        }
                        maxValue = mat[mid][j];
                        tagX = mid;
                        tagY = j;
                    }
                    return new int[]{tagX, tagY};
                }
            }

            if (mid == row - 1) {
                if (mat[tagX-1][tagY] < maxValue) {
                    return new int[]{tagX, tagY};
                } else {
                    mid --;
                    maxValue = -1;
                    for (int j = 0; j < col; j++) {
                        if (mat[mid][j] < maxValue) {
                            continue;
                        }
                        maxValue = mat[mid][j];
                        tagX = mid;
                        tagY = j;
                    }
                    return new int[]{tagX, tagY};
                }
            }

            if (mat[tagX-1][tagY] < maxValue && mat[tagX+1][tagY] < maxValue) {
                return new int[]{tagX, tagY};
            }

            if (mat[tagX-1][tagY] > maxValue) {
                down = tagX - 1;
            } else if (mat[tagX+1][tagY] > maxValue) {
                up = tagX + 1;
            }

        }

        return new int[]{-1,-1};

    }
}
